local Node = {}
Node.__cname = "util.BSTree.Node"
Node.__index = Node

function Node.new(v)
    local obj = {}
    setmetatable(obj, Node)
    obj:ctor(v)
    return obj
end

function Node:ctor(v)
    self.value = v
    self.left = nil
    self.right = nil
end


local BSTree = {}
BSTree.__cname = "util.BSTree"
BSTree.__index = BSTree

function BSTree.new(cmpFunc)
    local obj = {}
    setmetatable(obj, BSTree)
    obj:ctor(cmpFunc)
    return obj
end

function BSTree:ctor(cmpFunc)
    self.cmpFunc = cmpFunc
    self.count = 0
    self.root = nil
end

function BSTree:Clear()
    self.count = 0
    self.root = nil
end

function BSTree:GetCount()
    return self.count
end

function BSTree:Add(v)
    local newNode = Node.new(v)
    local node = self.root
    if nil == node then
        self.root = newNode
        self.count = self.count + 1
        return
    end

    while nil ~= node do
        local cmpResult = self.cmpFunc(v, node.value)
        if cmpResult < 0 then --小: 在左子树添加
            if nil == node.left then
                node.left = newNode
                break
            else
                node = node.left
            end
        elseif cmpResult > 0 then --大: 在右子树添加
            if nil == node.right then
                node.right = newNode
                break
            else
                node = node.right
            end
        else
            print(tostring(v), "have exist, ignore")
        end
    end
    self.count = self.count + 1
end

function BSTree:Contains(v)
    if self.count < 1 then return false end
    local node = self.root
    while nil ~= node do
        local cmpResult = self.cmpFunc(v, node.value)
        if cmpResult < 0 then
            node = node.left
        elseif cmpResult > 0 then
            node = node.right
        else
            return true
        end
    end
    return false
end

function BSTree:Remove(v)
    if self.count < 1 then return false end

    local parent = nil
    local node = self.root
    while nil ~= node do
        local cmpResult = self.cmpFunc(v, node.value)
        if cmpResult < 0 then
            parent = node
            node = node.left
        elseif cmpResult > 0 then
            parent = node
            node = node.right
        else
            self:_DelNode(node, parent)
            self.count = self.count - 1
            return true
        end
    end
    return false
end

function BSTree:_DelNode(delNode, delNodeParent)
    if nil == delNode.left and nil == delNode.right then --删除节点没有子节点, 直接删除(断开与parent的关系)
        if delNode == self.root then
            self.root = nil
        elseif delNodeParent.left == delNode then
            delNodeParent.left = nil
        elseif delNodeParent.right == delNode then
            delNodeParent.right = nil
        else
            print("error")
        end
    elseif nil == delNode.left then --删除节点只有右子节点, 断开与parent的关系, parent子节点直接指向那个右子节点
        if delNode == self.root then
            self.root = delNode.right
        elseif delNodeParent.left == delNode then
            delNodeParent.left = delNode.right
        elseif delNodeParent.right == delNode then
            delNodeParent.right = delNode.right
        else
            print("error")
        end
        delNode.right = nil --断开节点关系
    elseif nil == delNode.right then --删除节点只有左子节点, 断开与parent的关系, parent子节点直接指向那个左子节点
        if delNode == self.root then
            self.root = delNode.left
        elseif delNodeParent.left == delNode then
            delNodeParent.left = delNode.left
        elseif delNodeParent.right == delNode then
            delNodeParent.right = delNode.left
        else
            print("error")
        end
        delNode.left = nil --断开节点关系
    else --左右子节点都有, 右子树中找一个最小的节点替换到删除节点处
        local replaceNode, replaceNodeParent = self:_FindReplaceNode(delNode)
        delNode.value = replaceNode.value
        self:_DelNode(replaceNode, replaceNodeParent)
    end
end

function BSTree:_FindReplaceNode(delNode)
    local parent = delNode
    local node = delNode.right
    while nil ~= node do
        if nil ~= node.left then
            parent = node
            node = node.left
        else
            return node, parent
        end
    end
    print("error")
end

function BSTree:__tostring()
    if self.count < 1 then return "" end
    local strTb = {}
    local queue = {}
    table.insert(queue, self.root)

    while #queue > 0 do
        local node = queue[1]
        table.remove(queue, 1)
        table.insert(strTb, tostring(node.value))

        if nil ~= node.left then
            table.insert(queue, node.left)
        end
        if nil ~= node.right then
            table.insert(queue, node.right)
        end
    end
    return table.concat(strTb, ",")
end

return BSTree

--[[
function BSTree:FindMin()

end

function BSTree:FindMax()

end

function BSTree:FindFloor(v)

end

function BSTree:FindCeil(v)

end

function BSTree:Rank(v)

end

]]